package com.randomGraph;

import java.util.Arrays;

/**
 * 
 * @author Taranjeet singh bhatia
 * Date: 09/18/2011
 * pid: t2974589
 * 
 * This program generate Random graph of n vertex and p density
 * See RandomGraphTest for test programs
 */

public class RandomGraph {
	/**
	 * @param args
	 * 
	 */
	private boolean adjMatrix [][];
	//private int graphNodes[];
	private int degreeSquence[];
	private int vertexCount;
	private double graphDensity;
	private String name;

	/**
	 * @return name of Random graph
	 */
	public String getName() {
		return name;
	}
	/**
	 * @param To set name of Graph
	 * 
	 */
	public void setName(String name) {
		this.name = name;
	}
	
	/**
	 *Add edge in adjacency Matrix
	 * @param i 
	 * @param j 
	 */
	public void addEdge(int i, int j) {
		this.adjMatrix[i][j] = true;
		this.adjMatrix[j][i] = true;
	}
	
	/**
	 * Remove edge from adjacency Matrix
	 * @param i 
	 * @param j 
	 */
	public void removeEdge(int i, int j) {
		this.adjMatrix[i][j] = false;
		this.adjMatrix[j][i] = true;
	}
	
	
	/**
	 * To check edge between v1 and v2 vertices
	 * @param i
	 * @param j
	 * @return true/false
	 */
	public boolean isEdge(int i, int j) {
		if (this.adjMatrix[i][j] == true)
			return true;
		else return false;
	}
	
	/*
	 * Default constructor
	 */
	public RandomGraph() {
		this.adjMatrix = new boolean[0][0];
		
	}
	
	/**
	 * Random graph adjacency Matrix initialization
	 * @param vertex
	 */
	public RandomGraph(int vertex){
		
		this.vertexCount = vertex;
		this.adjMatrix = new boolean[vertex][vertex];
		this.degreeSquence = new int[vertex];
		
		for (int i = 0; i < vertex; i++) {
			for (int j = 0; j < vertex; j++) {
				this.adjMatrix[i][j] = false;
			}
			this.degreeSquence[i]= 0;
		}	
		setName("Random Graph of n= "+vertex);
		
	}
	
	/**
	 * Create Random graph adjacency Matrix for density p
	 * @param density
	 */
	public void createRandomGraph(double density) {
		this.graphDensity = density;
		setName("Random Graph of n= "+ this.vertexCount + " & density of "+ this.graphDensity);
		for (int i = 0; i < this.vertexCount; i++) {
			for (int j = 0; j < i; j++) {
				
				if (Math.random() <= this.graphDensity){
					addEdge(i, j);	
				}
				
				
			}
		}
	}
	
	
	/**
	 * Display Random Graph created using
	 * createRandomGraph() method
	 */
	public void displayRandomGraph() {
		System.out.println("Displaying " + getName());
		
		for (int i = 0; i < vertexCount; i++) {
			for (int j = 0; j < vertexCount; j++) {
				System.out.print(booleanToBinary(this.adjMatrix[i][j]) + "  ");
				
			}
			System.out.println();
			
		}
	}
	
	/**
	 * Display degree of sequence
	 * @param a
	 * 
	 * :"true" for sorted Non-increasing order, 
	 * :"false" for sorted Non-decreasing order
	 * 
	 */
	
	public void showDegreeSquence(boolean a) {
		int count = 0;
		for (int i = 0; i < this.vertexCount; i++) {
			count = 0;
			for (int j = 0; j < this.vertexCount; j++) {
				if (this.adjMatrix[i][j]){
					count++;
					
				}
				this.degreeSquence[i] = count;
			}
		}
		Arrays.sort(this.degreeSquence);
		
		System.out.println();
				
		if (a){
			//true for ascending order
			System.out.println("Degree Sequence of " + getName());
			System.out.println("Showing Degree Sequence in sorted Non-increasing order: ");
			
			System.out.println(Arrays.toString(this.degreeSquence));
		}else {
			//false for descending order
			int len = this.degreeSquence.length;
			for (int i = 0; i < len/2; i++) {
				int temp = this.degreeSquence[i];
				this.degreeSquence[i] = this.degreeSquence[len - 1 - i];
				this.degreeSquence[len - 1 -i] = temp;
			}
			System.out.println("Degree Sequence of " + getName());
			System.out.println("Showing Degree Sqeuence in sorted Non-decreasing order: ");
			System.out.println(Arrays.toString(this.degreeSquence));
		}
	}
	
	
	/**
	 * Converting binary to boolean
	 * @param b
	 * @return
	 */
	public byte booleanToBinary(boolean b) {
		if (b) return 1;
		else return 0;
				
	}
	
	
	public static void main(String[] args) {
		RandomGraph r1 = new RandomGraph(7);
		r1.createRandomGraph(0.4);
		r1.displayRandomGraph();
		r1.showDegreeSquence(true);
		r1.showDegreeSquence(false);
	}
	
	

}
